1. Field of the Invention
The present invention relates to load balancing methods and apparatus used for a computer system in which plural nodes (computers, in practice) are connected with each other via a network and each node processes an input task (message). This application is based on Japanese Patent Application No. Hei 8-200451, the contents of which are incorporated herein by reference.
2. Description of the Related Art
The computer systems in which plural computers (called "nodes", hereinafter) are connected to each other via a network are classified into two types according to the manner in which each task is accepted: one is a centralized arrival system in which all tasks are accepted by a single node (called a "task acceptance node") and the accepted tasks are distributed from the task acceptance node to other nodes; the other type is a distributed arrival system in which a task arrives at any node and the node accepts the task.
There are also two types of load balancing methods: one is a centralized control method in which one node in the system has load balancing processing equipment and only the node (having the load balancing processing equipment) performs load balancing processes; the other type is a distributed control method in which each node in the system has load balancing processing equipment and each node performs load balancing processes.
Regarding a load balancing method, used in such a computer system in which plural computers are connected with each other via a network, for balancing the load of each node by distributing loads of the entire system into each node and for minimizing a mean response time of the entire system, Japanese Patent Application, First Publication, No. Hei 7-152700 discloses a (performance-function uniform) system in which all nodes in the system are uniform in performance and functions, that is, possible functions to be processed are the same.
In such a performance-function uniform system, the system load can be balanced just by equalizing the number of tasks in each node. However, in a system in which nodes in the system are not uniform in their performance, processing times are different according to performance of each node; thus, the system load cannot be balanced just by equalizing the number of tasks of each node. If a load balancing method used for the performance-function uniform system is applied to such a "performance non-uniform" system, the following problems may occur.
1. Task assignment in accordance with performance of each node is not performed. Therefore, even if there is a node with high performance has reserve ability to process tasks, a task may be assigned to a node having lower performance. That is, if tasks are assigned to nodes with high performance, response times could be shorter and consequently, the mean response time of the system could be minimized. However, the minimization cannot be realized for the above reason.
2. Owing to the order of the nodes in the system arrangement, tasks may be assigned to the nodes starting at a node with lower performance and progressing to a node with higher performance. In this case, nodes with high performance are not sufficiently used, thus the mean response time cannot be minimized.
On the other hand, in a "function non-uniform" system (that is, the number and the kinds of executable tasks are different with respect to each node), the system load cannot be balanced by using the above-mentioned load balancing method used for a performance-function uniform system because the number of steps to be performed is different for each function, and because the number of nodes which can execute a function is different for each function in the system. If applying a load balancing method used for the performance-function uniform system to such a "performance uniform but function non-uniform" system, the following problems may occur.
1. In the above load balancing method used for the performance-function uniform system, tasks are assigned to each node without distinguishing tasks belonging to functions which many nodes in the system can execute from tasks belonging to functions which fewer nodes can execute. Therefore, even if it is possible to assign a "task belonging to a function which many nodes can execute" to a node which cannot execute a "task belonging to a function which fewer nodes can execute", the task (belonging to a function which many nodes can execute) may be assigned to a node which can execute tasks of both types, and thus a task belonging to the former type (that is, a task belonging to a function which fewer nodes can execute) might circulate in the network while waiting to be processed. In this case, the response time increases.
2. When the number of steps of an executable program to be performed is different for each function, a task having a large number of steps must be processed by the node with the lowest possible load at the time (that is, a node having sufficient resources for processing). However, in the load balancing method used for a function uniform system, tasks are assigned so as to equalize the number of tasks assigned to each node regardless of the number of steps of an executable program; thus, processing of an assigned task having a large total number of steps of an executable program may be delayed in the relevant node. Accordingly, the response time of a task assigned to such a node increases, thus the mean response time of the entire system is not minimized.
On the other hand, in order to balance loads in the distributed arrival system, it is necessary to transfer a task which arrived at any node to another node.
As a conventional transfer algorithm, "sender initiated" and "receiver initiated" algorithms are known. The sender initiated algorithm is effective when the load of the entire system is low. However, if the load of the entire system becomes high, the mean response time increases and the system becomes unstable. In contrast, the receiver initiated algorithm is effective when the load of the entire system is high. However, when the load of the entire system is low, the mean response time is larger than that of the sender initiated algorithm. In either algorithm, information relating to loads of other nodes is not managed, and after the necessity of task transfer occurs, selection of a source or destination node is started. Therefore, it takes a lot of time before actual task transfer is started, that is, before the load is balanced.
Furthermore, in the distributed control method, information exchange between a node and another node is performed so as to select a source or a destination node; thus, network traffic of the entire system increases. As a result, a time necessary for task transfer increases and the net amount of decrease of the mean response time is small.
That is, in the above-mentioned conventional load balancing methods, there has been a problem in that if the method is applied to a system in which nodes are non-uniform in performance, task assignment in consideration of performance of each node cannot be performed whereby mean response times are not balanced between the nodes and the means response time of the entire system is not minimized.
Also in the above-mentioned conventional load balancing methods, there has been another problem in that if the method is applied to a system in which nodes are non-uniform in the kinds and the number of executable functions, tasks are assigned without consideration of the number of the nodes which can execute each task, a load for each function, and the number of steps in an executable problem for each node; therefore, the response time of a function may be larger and loads of the nodes are not balanced and thus the mean response time of the entire system is not minimized.